package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description  两个链表的第一个公共结点
 *
 * <p> 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
 * （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 *
 * 数据范围：n <= 1000
 * 要求：空间复杂度：O(1)，时间复杂度：O(n)
 * </p>
 *
 * @date 2021/11/1 7:54
 **/
public class FindFirstCommonNode {

    public static void main(String[] args) {

    }

    /**
     * 非常巧妙：
     * 1、利用双指针遍历，构造出相同的链表长度；
     * 2、没有公共节点时，利用都为null，跳出循环！
     *
     * @param pHead1
     * @param pHead2
     * @return
     */
    static ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode t1 = pHead1;
        ListNode t2 = pHead2;

        while (t1 != t2) {
            t1 = t1 == null ? pHead2 : t1.next;
            t2 = t2 == null ? pHead1 : t2.next;
        }

        return t1;
    }


}
